package org.gushi.algorithm.a02;

public class QuickSort<E extends Comparable<E>> {


    private E[] list;


    public QuickSort(E[] list) {
        this.list = list;
    }

    public E[] listSort(){
//        return listSort("ASC");
        return null;
    }
    /**
     * 快速排序算法
     * O(n^2)
     * @return
     */
    public E[] listSort(int left,int right){

        if (left >= right) {
            return list;
        }

        E element = list[left];
        int l = left;
        int r = right;
        while (l<r){
            while (l<r){
                if(element.compareTo(list[r])>0){//如果元素比element小   元素在左边
                    list[l] = list[r];
                    break;
                }
                r--;
            }
            while (l<r){
                if(element.compareTo(list[l])<0){
                    list[r] = list[l];
                    break;
                }
                l++;
            }
        }
        System.out.println("i:"+l+",r:"+r);
        list[l] = element;

        for (int i = 0; i < list.length; i++) {
            System.out.print(list[i]);
            System.out.print(",");
        }


        listSort(left,l-1);
        listSort(l+1,right);


        return list;
    }


    /*
     * 快速排序
     *
     * 参数说明:
     *     a -- 待排序的数组
     *     l -- 数组的左边界(例如，从起始位置开始排序，则l=0)
     *     r -- 数组的右边界(例如，排序截至到数组末尾，则r=a.length-1)
     */
    public static void quickSort(int[] a, int l, int r) {

        if (l < r) {
            int i,j,x;

            i = l;
            j = r;
            x = a[i];
            while (i < j) {
                while(i < j && a[j] > x)
                    j--; // 从右向左找第一个小于x的数
                if(i < j)
                    a[i++] = a[j];
                while(i < j && a[i] < x)
                    i++; // 从左向右找第一个大于x的数
                if(i < j)
                    a[j--] = a[i];
            }
            a[i] = x;
            System.out.println("左侧---左边："+l+",右边："+(i-1));
            quickSort(a, l, i-1); /* 递归调用 */
            System.out.println("右侧：左边："+i+1+",右边："+r);
            quickSort(a, i+1, r); /* 递归调用 */
        }
    }


}
